package prefix_sum;

import java.util.HashMap;

/**
 * @Description 剑指 Offer II 011. 0 和 1 个数相同的子数组
 * @Author Firenut
 * @Date 2023-04-22 10:16
 */
public class II0111_findMaxLength {
    // 求0,1个数相同的子数组问题,可转化为求前缀和为0的子数组问题
    // 规定: 遇到0减1,遇到1加1(不需要前缀和数组,减低空间复杂度)
    // 当前缀和为0,说明0,1的个数相同
    // 利用HashMap存储前缀和 与 最后一个元素的下标 映射关系
    // 如果HashMap中存在相同的prefixSum,说明在当前index和之前某一个index之间的子数组和为0
    // 否则将键值对加入到map中
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    public int findMaxLength(int[] nums) {
        int prefixSum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1); //必须要先初始化
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                prefixSum--;
            } else {
                prefixSum++;
            }
            if (map.containsKey(prefixSum)) {
                int index = map.get(prefixSum);
                maxLen = Math.max(maxLen, i - index);
            } else {
                map.put(prefixSum, i);
            }
        }
        return maxLen;
    }
}
